package travellersalesman;

import java.io.InputStream;
import java.util.ArrayList;

import classictravellersalesman.*;

public class ExtendetGraph extends Graph {
	private static final int COMPLETE = 1;
	private static final int MIDDLE = 2;
	private static final int RARE = 3;
	
	protected int floydMatrix[][];
	protected double distanceMatrix[][];
	public ExtendetGraph() {
		super();
	}
	
	public ExtendetGraph(InputStream in) {
		super(in);
		floydMatrix = new int[vertexCount][];
		distanceMatrix = new double[vertexCount][];
		
		for(int i = 0; i < vertexCount;++i) {
			floydMatrix[i] = new int[vertexCount];
			distanceMatrix[i] = new double[vertexCount];
			for (int j = 0; j < vertexCount; j++) {
				distanceMatrix[i][j] = matrix[i][j];
				if(matrix[i][j] < ExtendetGraph.INF) {
					floydMatrix[i][j] = i;
				}
				else {
					floydMatrix[i][j] = -1;
				}				
			}
		}
		
		for(int k=0 ;k<vertexCount;++k ) {
			for(int i=0; i<vertexCount; ++i) {
				for(int j=0; j<vertexCount; ++j) {
					if(distanceMatrix[i][j] > distanceMatrix[i][k] + distanceMatrix[k][j]) {
						distanceMatrix[i][j] = distanceMatrix[i][k] + distanceMatrix[k][j];
						floydMatrix[i][j] = floydMatrix[k][j];
					}
				}
			}
		}
		
	}
	
	@Override
	public double getDistance(int i, int j) {
		return distanceMatrix[i][j];
	}
	
	public ArrayList<Integer> getPath(int i, int j) {
		ArrayList<Integer> result = new ArrayList<Integer>();
		result.add(j);
		while(floydMatrix[i][result.get(0)] != i) {
			result.add(0, floydMatrix[i][result.get(0)]);
		}
		result.add(0, i);
		return result;
	}
}
